package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}17:22
 */
public class LeetCode416 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1){
            return false;
        }
        int index = sum / 2;
        boolean[] dp = new boolean[index + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = index; i>= num; i--){
                if (dp[i - num]){
                    dp[i] = true;
                }
            }
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        int[] index = {1,5,11,5};
        System.out.println(new LeetCode416().canPartition(index));
    }
}
